package com.love.slidingWindow;

public class CanCompleteCircuit {


    public static void main(String[] args) {
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
//        int i = canCompleteCircuit(gas, cost);
        int i = can2(gas, cost);

        System.out.println(i);
    }

    //int[] gas = {1,2,3,4,5};
    //int[] cost = {3,4,5,1,2};
    //int[] r =   {-2，-2，-2，3，3}
    // 从 s 位置 转一圈 的累加和，只要不小于0，就可继续往前走，反之，从 s 位置开始，是走不通的

    //
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        //  r ：窗口即将进来数字的位置
        // len: 窗口大小（窗口里有几个数）
        // sum: 窗口累加和
       int n = gas.length;
       for (int l = 0,r = 0,len = 0,sum = 0; l < n; l++){
           while (sum >= 0){ // 这个地方只要是正数就可以
               if(len == n){ //这个边界条件也是相当牛逼（表示 l 和 r 相差一圈，）,（和后面式子的 先后顺序也值得思考）
                   return l;
               }
               len++; // 联合下面的式子，就代表 r 在这个圈，往一个方向移动
               r = (l + len) % n; // 这个式子表示环的移动，确实可以（和Hash取模统一原理）

               sum += gas[r] - cost[r];
           }
           len--;
           sum -= gas[l] - cost[l];
       }
     return -1;
    }



    public static int can2(int[] gas, int[] cost){
        int len = gas.length;
        int spare = 0;
        int minSpare = Integer.MAX_VALUE;
        int minIndex = 0;
        for (int i = 0; i < len; i++) {
            spare += gas[i] - cost[i];
            if (spare < minSpare) {
                minSpare = spare;
                minIndex = i;
            }
        }
        return spare < 0 ? -1 : (minIndex + 1) % len;
    }

}
